package oj;

/**
 * 快速排序的partition解决第k大元素问题
 */
public class Num215 {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,0,nums.length-1,nums.length-k);
    }

    private int  quickSort(int[] nums, int l, int r,int n) {
        if(l>r){
            return -1;
        }
        int p=partition(nums,l,r);//每一次分区函数都能将一个分区元素放到最终的位置
        //分区函数返回的索引下标刚好可以用来判定该元素是不是要找的第k大元素(第k大元素下标：length-k)
        //当分区函数返回的索引值=n-k，该分区元素就是我们要找的元素
        if(p<n){
           return quickSort(nums,p+1,r,n);
        }else if(p==n){
            return nums[p];
        }else {
           return quickSort(nums, 0, p - 1,n);
        }
    }

    private int partition(int[] nums, int l, int r) {
        int v=nums[l];
        int j=l;
        for (int i = l+1; i <=r; i++) {
            if(nums[i]<v){
                swap(nums,j+1,i);
                j++;
            }
        }
        swap(nums,l,j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}
